#include "template.h"

/* 并查集数据结构 */
struct DSU {
    /* 父节点数组 */
    vector<int> f;
    /* 组大小数组 */
    vector<int> siz;

    /* 默认构造函数 */
    DSU() {}

    /* 带参数的构造函数，初始化并查集 */
    DSU(int n) {
        init(n);
    }

    /* 初始化并查集，设置所有节点的父节点为自身，组大小为1 */
    void init(int n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    /* 查找节点x的根节点，并进行路径压缩 */
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    /* 判断节点x和节点y是否属于同一个组 */
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    /* 合并节点x和节点y所在的组 */
    /* 如果x和y已经属于同一个组，则不进行合并，返回false */
    /* 否则，将x和y所在的组合并，并更新组大小，返回true */
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    /* 返回节点x所在组的大小 */
    int size(int x) {
        return siz[find(x)];
    }
};
